package hash_1114;

import java.util.Collections;
import java.util.Random;
import java.util.TreeSet;

// 元素类型：long 类型
// 元素取值范围：>= 0
// 哈希函数：除留余数法：key % array.length
/*
如何检查这个哈希表对象是正确的：
1. 表中存的 key 的个数 == size
2. 表中的 key 不应该出现重复
3. 每条链表的所有 key 的 hash 值应该是一样的，都应该等于 hashCode(链表的第一个key）
 */
public class HashTableV1 {
    static class ListNode {
        long key;
        ListNode next;

        ListNode(long key) {
            this.key = key;
        }
    }

    private ListNode[] array;
    private int size;

    public HashTableV1() {
        array = new ListNode[7];
        size = 0;
    }

    public boolean add(long key) {
        int index = hashCode(key);
        // 需要确保 key 不能重复插入
        for (ListNode cur = array[index]; cur != null; cur = cur.next) {
            if (cur.key == key) {
                // 重复了
                return false;
            }
        }

        // key 不存在的
        // 头插 / 尾插理论上都可以
        ListNode node = new ListNode(key);
        node.next = array[index];
        array[index] = node;
        size++;

        // TODO：由于负载因子过大，需要扩容
        if (1.0 * size / array.length > 0.75) {
            统计信息();
            grow();
        }

        return true;
    }

    private void 统计信息() {
        System.out.println("当前情况：");
        System.out.println("元素个数 = " + size);
        System.out.println("数组长度 = " + array.length);
        System.out.println("元素个数 / 数组长度 = " + (1.0 * size / array.length));

        long sum = 0;
        long max = Long.MIN_VALUE;
        int slots = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == null) {
                continue;
            }

            // 只统计链表不为空链表的情况
            slots++;
            int listSize = 0;
            for (ListNode cur = array[i]; cur != null; cur = cur.next) {
                listSize++;
            }

            sum += listSize;
            if (listSize > max) {
                max = listSize;
            }
        }
        double avg = 1.0 * sum / slots;
        System.out.println("链表平均长度 = " + avg);
        System.out.println("链表最长长度 = " + max);
        System.out.println("================================");
    }

    private void grow() {
        ListNode[] newArray = new ListNode[this.array.length * 2];
        for (int i = 0; i < array.length; i++) {
            ListNode cur = array[i];
            while (cur != null) {
                int index = (int)cur.key % newArray.length;

                ListNode next = cur.next;
                cur.next = newArray[index];
                newArray[index] = cur;

                cur = next;
            }
        }

        this.array = newArray;
    }

    public boolean remove(long key) {
        int index = hashCode(key);

        if (array[index] == null) {
            return false;
        }

        // 头删的情况
        if (array[index].key == key) {
            array[index] = array[index].next;
            size--;
            return true;
        }

        ListNode prev = array[index];
        ListNode cur = array[index].next;
        while (cur != null) {
            if (cur.key == key) {
                prev.next = cur.next;
                size--;
                return true;
            }

            prev = cur;
            cur = cur.next;
        }

        return false;
    }

    // 数据规模：size
    // 时间复杂度（平均）：O(1)
    public boolean contains(long key) {
        // 1. 把 key 转成下标 —— 求哈希值的过程
        int index = hashCode(key);
        // 2. 要查找的链表的头结点就是
        // 断言：index 是不会越界了
        ListNode head = array[index];
        // 3. 遍历链表，查找对应的 key 是否存在
        for (ListNode cur = head; cur != null; cur = cur.next) {
            if (cur.key == key) {
                return true;
            }
        }

        return false;
    }

    private int hashCode(long key) {
        return (int)key % array.length;
    }



    public void check() {
        // 遍历计算所有的 key 的个数
        TreeSet<Long> set = new TreeSet<>();
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            // array[i]
            int hash = -1;
            for (ListNode cur = array[i]; cur != null; cur = cur.next) {
                assertTrue(set.contains(cur.key) == false);
                set.add(cur.key);

                if (hash == -1) {
                    hash = hashCode(cur.key);
                } else {
                    assertTrue(hashCode(cur.key) == hash);
                }
                count++;
            }
        }

        assertTrue(count == size);
    }

    private static void assertTrue(boolean condition) {
        if (!condition) {
            throw new RuntimeException();
        }
    }

    public static void main(String[] args) {
        long[] array = new long[1000];
        for (int i = 0; i < 1000; i++) {
            array[i] = i;
        }
        shuffle(array);

        HashTableV1 t = new HashTableV1();
        for (long key : array) {
            t.add(key);
            t.check();
        }
    }

    private static void shuffle(long[] array) {
        Random rnd = new Random();
        for (int i = array.length; i > 1; i--)
            swap(array, i-1, rnd.nextInt(i));
    }

    private static void swap(long[] array, int i, int j) {
        long t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}
